Menemukan Cepat &
Mengurutkan Akurat
👩🏫 Secara Formal:
Pencarian (Searching) adalah algoritma untuk menemukan posisi sebuah elemen di dalam himpunan data. Terdapat dua algoritma umum: Linear Search (mencari satu per satu dari awal, kompleksitas O(N)) dan Binary Search (membelah dua area pencarian pada array yang sudah terurut, kompleksitas O(log N)).
Pengurutan (Sorting) adalah proses menyusun elemen data ke dalam urutan tertentu (misal naik/turun). Algoritma dasar seperti Bubble Sort dan Insertion Sort memiliki kompleksitas O(N²), sedangkan algoritma mahir seperti Merge Sort memiliki kompleksitas O(N log N).
Analogi Jaman Now
Linear vs Binary Search
Bayangin kamu lagi cari akun Instagram teman yang namanya berawalan huruf 'M'. Kalau pakai Linear Search, kamu scroll followers kamu satu-satu dari awal sampai ketemu (Bisa lama banget!). Tapi kalau Binary Search, kayak kamu buka buku telepon fisik, langsung belah di tengah, lihat halamannya. "Oh ini huruf K, berarti M ada di sebelah kanan." Kamu belah lagi sisi kanan, sampai pas ketemu. Sangat cepat! Tapi syaratnya bukunya harus urut abjad.
Insertion Sort
Kayak kalau kamu lagi main kartu Uno. Setiap dapat kartu baru dari tumpukan, kamu pasti menyelipkan kartu itu ke posisi yang benar di tanganmu supaya tetap urut dari kecil ke besar. Begitulah Insertion Sort bekerja: mengambil satu elemen, dan menyisipkannya ke posisi yang benar di antara elemen yang sudah diurutkan sebelumnya.
⚠️ Common Mistakes di OSN
- Lupa Mengurutkan Data: Melakukan Binary Search pada array yang belum terurut. Binary Search WAJIB dilakukan pada data yang sorted. Jika tidak, hasilnya akan selalu salah/tidak terprediksi.
- Miskonsepsi Kompleksitas: Mengira Sorting + Binary Search selalu lebih cepat daripada Linear Search. Jika hanya mencari satu angka satu kali, Linear Search O(N) lebih cepat daripada Sort+BS O(N log N). Sort+BS hanya untung jika kita melakukan banyak query pencarian sekaligus!
Cara Kerja Binary Search
Lihat bagaimana algoritma ini dengan cepat mencari angka target pada array yang sudah terurut dengan membelah dua rentang pencarian berulang kali.
Visualisasi: Array dengan indeks 0-14. L (Left), R (Right), dan Mid. Jika `arr[Mid]` lebih kecil dari target, L geser ke Mid+1.
⚠️ Common Mistakes: Integer Overflow pada Mid
Saat menghitung indeks tengah di C++, jangan menggunakan: int mid = (L + R) / 2;
Alasan: Jika array sangat besar dan L serta R adalah angka miliaran, penjumlahan L + R bisa melebihi batas maksimal tipe data int (yaitu ~2.1 miliar), menyebabkan Integer Overflow dan program error.
Solusi Trik OSN: Gunakan rumus int mid = L + (R - L) / 2; untuk mencegah overflow!
Simulator Bubble Sort
Jalankan proses pengurutan langkah demi langkah. Bubble Sort akan terus membandingkan dua elemen bersebelahan dan menukarnya jika urutannya salah.
Kontrol Lab
Tekan "Next Step" untuk memulai.